﻿#define _CRT_SECURE_NO_WARNINGS 1

//根据⼆叉树创建字符串
//https://leetcode.cn/problems/construct-string-from-binary-tree/
//给你二叉树的根节点 root ，
//请你采用前序遍历的方式，
//将二叉树转化为一个由括号和整数组成的字符串，
//返回构造出的字符串。
//
//空节点使用一对空括号对 "()" 表示，
//转化后需要省略所有不影响字符串
//与原始二叉树之间的一对一映射关系的空括号对

//class Solution {
//public:
//	// ⾛前序遍历⼆叉树转换
//	string tree2str(TreeNode* root) {
//		if (root == nullptr)
//			return "";
//
//		string ret = to_string(root->val);
//		// 1、左右都为空，要省略括号
//		// 2、右为空，要省略括号
//		// 3、左为空，右不为空，不能省略括号
//
//		// 左边和右边有⼀个为空，左边必须有括号
//		if (root->left || root->right)
//		{
//			ret += '(';
//			ret += tree2str(root->left);
//			ret += ')';
//		}
//		if (root->right)
//		{
//			ret += '(';
//			ret += tree2str(root->right);
//			ret += ')';
//		}
//		return ret;
//	}
//};


//⼆叉树的层序遍历
// https://leetcode.cn/problems/binary-tree-level-order-traversal/
// 
//给你二叉树的根节点 root ，
//返回其节点值的 层序遍历 。 
//（即逐层地，从左到右访问所有节点）
//⼆叉树的层序遍历II
// https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
// 
//给你二叉树的根节点 root ，
//返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，
//逐层从左向右遍历）
//
//class Solution {
//public:
//	vector<vector<int>> levelOrder(TreeNode* root) {
//		vector<vector<int>> vv;
//		queue<TreeNode*> q;
//		int levelSize = 0;
//		if (root)
//		{
//			q.push(root);
//			levelSize = 1;
//		}
//		while (!q.empty())
//		{
//			vector<int> v;
//
//			// 控制⼀层出完
//			while (levelSize--)
//			{
//				TreeNode* front = q.front();
//				q.pop();
//				v.push_back(front->val);
//				if (front->left)
//					q.push(front->left);
//
//				if (front->right)
//					q.push(front->right);
//			}
//			// 当前层出完了，下⼀层都进队列了，队列size就是下⼀层数据个数
//			levelSize = q.size();
//
//			// 获取到每⼀层数据放到⼆维数组中
//			vv.push_back(v);
//		}
//		return vv;
//	}
//};



//⼆叉树的最近公共祖先
// https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
// 
//给定一个二叉树, 
//找到该树中两个指定节点的最近公共祖先。
//
//百度百科中最近公共祖先的定义为：
//“对于有根树 T 的两个节点 p、q，
//最近公共祖先表示为一个节点 x，满足 x 
//是 p、q 的祖先且 x 的深度尽可能大
//（一个节点也可以是它自己的祖先）。”
//
//class Solution {
//public:
//	// 查找x是否在树中
//	bool IsInTree(TreeNode* root, TreeNode* x)
//	{
//		if (root == nullptr)
//			return false;
//
//		return root == x
//			|| IsInTree(root->left, x)
//			|| IsInTree(root->right, x);
//	}
//	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//		if (root == NULL)
//			return NULL;
//
//		if (root == p || root == q)
//		{
//			return root;
//		}
//
//		// 这⾥要注意，这⾥的命名⾮常关键，命名好了，代码可读性⼤⼤增强
//		bool pInLeft, pInRight, qInLeft, qInRight;
//
//		// 题⽬中有说明p和q⼀定是树中的结点
//		// p不在左树就在右树
//		pInLeft = IsInTree(root->left, p);
//		pInRight = !pInLeft;
//
//		// q不在左树就在右树
//		qInLeft = IsInTree(root->left, q);
//		qInRight = !qInLeft;
//		// ⼀个在左，⼀个在右，那么root就是最近公共祖先
//		// 都在左，递归去左树查找
//		// 都在右，递归去右树查找
//		if ((pInLeft && qInRight) || (qInLeft && pInRight))
//		{
//			return root;
//		}
//		else if (pInLeft && qInLeft)
//		{
//			return lowestCommonAncestor(root->left, p, q);
//		}
//		else if (pInRight && qInRight)
//		{
//			return lowestCommonAncestor(root->right, p, q);
//		}
//
//		// 虽然执⾏逻辑不会⾛到这⾥，但是如果不写这个代码，语法逻辑过不去(相当于语法上⾛
//		到这没返回值)
//		// 编译器会报语法错误。
//		assert(false);
//		return NULL;
//	}
//};
//class Solution {
//public:
//	bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
//	{
//		if (root == nullptr)
//			return false;
//
//		// 前序遍历的思路，找x结点的路径
//// 遇到root结点先push⼊栈，因为root就算不是x，但是root可能是根->x路径中⼀个分
//		⽀结点
//			path.push(root);
//		if (root == x)
//			return true;
//		if (GetPath(root->left, x, path))
//			return true;
//		if (GetPath(root->right, x, path))
//			return true;
//
//		// 如果左右⼦树都没有x，那么说明上⾯⼊栈的root不是根->x路径中⼀个分⽀结点
//		// 所以要pop出栈，回退，继续去其他分⽀路径进⾏查找
//		path.pop();
//
//		return false;
//	}
//	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//		stack<TreeNode*> pPath, qPath;
//		GetPath(root, p, pPath);
//		GetPath(root, q, qPath);
//		// 模拟链表相交，两个路径找交点
//		// ⻓的先⾛差距步，再⼀起⾛找交点
//		while (pPath.size() != qPath.size())
//		{
//			if (pPath.size() > qPath.size())
//				pPath.pop();
//			else
//				qPath.pop();
//		}
//		while (pPath.top() != qPath.top())
//		{
//			pPath.pop();
//			qPath.pop();
//		}
//		return pPath.top();
//	}
//};


//将⼆叉搜索树转化为排序的双向链表
// https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
// 
//将一个 二叉搜索树 
//就地转化为一个 已排序的双向循环链表 。
//
//对于双向循环列表，
//你可以将左右孩子指针作为双向循环链表的前驱和
//后继指针，第一个节点的前驱是最后一个节点，
//最后一个节点的后继是第一个节点。
//
//特别地，我们希望可以 就地 完成转换操作。
//当转化完成以后，树中节点的左指针需要指向前驱，
//树中节点的右指针需要指向后继。
//还需要返回链表中最小元素的指针。

//
//class Solution {
//public:
//	void InOrderConvert(Node* cur, Node*& prev)
//	{
//		if (cur == nullptr)
//			return;
//		// 中序遍历
//		InOrderConvert(cur->left, prev);
//		// 当前结点的左，指向前⼀个结点
//		cur->left = prev;
//		// 前⼀个结点的右，指向当前结点
//		if (prev)
//			prev->right = cur;
//
//		prev = cur;
//		InOrderConvert(cur->right, prev);
//	}
//	Node* treeToDoublyList(Node* root) {
//		if (root == nullptr)
//			return nullptr;
//		Node* prev = nullptr;
//		InOrderConvert(root, prev);
//
//		// 从根开始往左⾛，找到第⼀个结点
//		Node* head = root;
//		while (head->left)
//		{
//			head = head->left;
//		}
//
//		// head为第⼀个结点，prev是最后⼀个结点
//		// 题⽬要求为循环链表，进⾏⼀些链接
//		head->left = prev;
//		prev->right = head;
//		return head;
//	}
//};



//从前序与中序遍历序列构造⼆叉树
// https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
// 
//给定两个整数数组 preorder 和 inorder ，
//其中 preorder 是二叉树的先序遍历，
//inorder 是同一棵树的中序遍历，
//请构造二叉树并返回其根节点。


//从中序与后序遍历序列构造⼆叉树
// https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
// 
//给定两个整数数组 inorder 和 postorder ，
//其中 inorder 是二叉树的中序遍历， 
//postorder 是同一棵树的后序遍历，
//请你构造并返回这颗 二叉树 。

//class Solution {
//public:
//	TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int&
//		prei, int inbegin, int inend) {
//		if (inbegin > inend)
//			return nullptr;
//
//		// 前序确定根
//		TreeNode* root = new TreeNode(preorder[prei++]);
//
//		// 根分割中序左右⼦区间
//		int rooti = inbegin;
//		while (rooti <= inend)
//		{
//			if (inorder[rooti] == root->val)
//				break;
//			else
//				rooti++;
//		}
//
//		// 递归左右⼦区间，递归构建左右⼦树
//		// [inbegin, rooti-1] rooti [rooti+1, inend]
//		root->left = _buildTree(preorder, inorder, prei, inbegin, rooti - 1);
//		root->right = _buildTree(preorder, inorder, prei, rooti + 1, inend);
//		return root;
//	}
//
//	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
//		int i = 0;
//		TreeNode* root = _buildTree(preorder, inorder, i, 0, inorder.size() - 1);
//		return root;
//	}
//};

//二叉树的前序遍历
// https://leetcode.cn/problems/binary-tree-preorder-traversal/
// 
//给你二叉树的根节点 root ，
//返回它节点值的 前序 遍历。
//
//
//二叉树的中序遍历
// https://leetcode.cn/problems/binary-tree-inorder-traversal/
// 
//给定一个二叉树的根节点 root ，
//返回 它的 中序 遍历 。
//
//
//. 二叉树的后序遍历
// https://leetcode.cn/problems/binary-tree-postorder-traversal/
// 
//给你一棵二叉树的根节点 root ，
//返回其节点值的 后序遍历

//class Solution {
//public:
//	vector<int> preorderTraversal(TreeNode* root) {
//		stack<TreeNode*> s;
//		vector<int> v;
//		TreeNode* cur = root;
//		while (cur || !s.empty())
//		{
//			// 访问⼀颗树的开始
//			// 1、访问左路结点，左路结点⼊栈
//			while (cur)
//			{
//				v.push_back(cur->val);
//				s.push(cur);
//				cur = cur->left;
//			}
//			// 2、从栈中依次访问左路结点的右⼦树
//			TreeNode* top = s.top();
//			s.pop();
//			// 循环⼦问题⽅式访问左路结点的右⼦树 -- 
//			cur = top->right;
//		}
//		return v;
//	}
//};
//class Solution {
//public:
//	vector<int> inorderTraversal(TreeNode* root) {
//		stack<TreeNode*> st;
//		TreeNode* cur = root;
//		vector<int> v;
//		while (cur || !st.empty())
//		{
//			// 访问⼀颗树的开始
//			// 1、左路结点⼊栈
//			while (cur)
//			{
//				st.push(cur);
//				cur = cur->left;
//			}
//			// 访问问左路结点 和 左路结点的右⼦树
//			TreeNode* top = st.top();
//			st.pop();
//			v.push_back(top->val);
//			// 循环⼦问题⽅式访问右⼦树
//			cur = top->right;
//		}
//		return v;
//	}
//};
//class Solution {
//public:
//	vector<int> postorderTraversal(TreeNode* root) {
//		TreeNode* cur = root;
//		stack<TreeNode*> s;
//		vector<int> v;
//		TreeNode* prev = nullptr;
//		while (cur || !s.empty())
//		{
//			// 1、访问⼀颗树的开始
//			while (cur)
//			{
//				s.push(cur);
//				cur = cur->left;
//			}
//			TreeNode* top = s.top();
//			// top结点的右为空 或者 上⼀个访问结点等于他的右孩⼦
//			// 那么说明(空)不⽤访问 或者 (不为空)右⼦树已经访问过了
//			// 那么说明当前结点左右⼦树都访问过了，可以访问当前结点了
//			if (top->right == nullptr || top->right == prev)
//			{
//				s.pop();
//				v.push_back(top->val);
//				prev = top;
//			}
//			else
//			{
//				// 右⼦树不为空，且没有访问，循环⼦问题⽅式右⼦树
//				cur = top->right;
//			}
//		}
//		return v;
//	}
//};
